package library;

public class FloydWarshall {
	int next[][];
	/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
	 * (infinity if there is none).
	 * Also assume that n is the number of vertices and edgeCost(i,i) = 0
	 * */
	int path[][];
	/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
	 * from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
	 * edgeCost(i,j) or infinity if there is no edge between i and j.
	 */

	public void floydwarshall (){
		for (int k =0; k<path.length; k++)
			for (int i =0; i<path.length; i++)
				for (int j =0; j<path.length; j++)
					path[i][j] = Math.min ( path[i][j], path[i][k]+path[k][j] );
	}

	public void FloydWarshallWithPathReconstruction (){
		for (int k =0; k<path.length; k++)
			for (int i =0; i<path.length; i++)
				for (int j =0; j<path.length; j++)
					if (path[i][k] + path[k][j] < path[i][j] ){
						path[i][j] = path[i][k]+path[k][j];
						next[i][j] = k;
					}
	}
	public int GetPath (int i, int j){
		return GetPath(i,next[i][j]) + next[i][j] + GetPath(next[i][j],j);
	}

	/*
	 * NOTE: pathLength==i actually is a path of length i+1
	 * (so we use index 0).
	 */
	int[][][] next3d;
	int[][][] path3d;

	public void FloydWarshall3DWithPathReconstruction (int pathLength){
		int prev = pathLength-1;
		for (int k =0; k<path3d.length; k++)
			for (int i =0; i<path3d.length; i++)
				for (int j =0; j<path3d.length; j++)
					if (path3d[i][k][prev] + path3d[k][j][0] < path3d[i][j][pathLength] ){
						path3d[i][j][pathLength] = path3d[i][k][prev]+path3d[k][j][0];
						next3d[i][j][pathLength] = k;
					}
	}
	
	public void GetPath3dBegin(int start, int end, int pathLength){
		System.out.print(start);
		GetPath3d(start,end,pathLength);
		System.out.println(" "+end);
	}
	
	public void GetPath3d(int i, int j, int k){
		if(k>0){
			GetPath3d(i,next3d[i][j][k],k-1);
			System.out.print(" "+(1+next3d[i][j][k]));
		}
	}
}
